#include<iostream>
#include<vector>
using namespace std;


namespace Mango
{
//使用闭散列实现哈希表的时候需要使用一个状态来标识每一个位置
//原因：我们在哈希表当中查找一个元素是否存在的时候，使用的是线性查找，如果找到空位置还没有找到，说明该元素不存在
//假设我们不设置状态的话，如果该元素曾经被删除了，我们也能找到
//
//设置状态之后： 插入的时候：计算出哈希地址之后线性探测/二次探测，找到状态为空或者状态为删除的位置进行插入
//查找的时候：计算出哈希地址之后，线性遍历，若当前位置为存在或者当前位置为删除就一直线性探测/二次探测，如果遍历到空还没有找到，说明哈希表当中不存在该元素,值匹配且当前位置状态为存在才算是找到该元素
enum Status
{
  EXIST,
  EMPTY,
  DELETE
};

//哈希表节点
template<class K,class V>
struct HashNode
{
  pair<K,V> _kv;
  Status status; //必须要初始化，否则状态就是随机值
  HashNode() : status(EMPTY)
  {}
  HashNode(const pair<K,V>& kv) :_kv(kv)
  {}
};
template<class K,class V>
class HashTable
{
public:
  typedef HashNode<K,V> Node;//哈希表节点类型
  HashTable() :n(0)
  {}
  bool insert(const pair<K,V>& kv)
  {
   if(find(kv.first) != nullptr) //数据冗余则不插入
     return false;
   //检查是否需要扩容:最初哈希表为空 || 负载因子>0.7
   //负载因子 = 表中有效元素个数 / 哈希表的大小
   if(tables.size() == 0 || (double)n / (double)tables.size() > 0.7)
   {
      size_t newCapacity = tables.size() == 0 ? 10:tables.size()*2;
      //把原来表中的数据复用insert函数重新计算哈希地址插入到新表当中
      //注意：！！！不是所有数据都需要插入,必须要该位置的状态为存在的元素才能插入
      //因为要复用insert函数，所以需要创建的是哈希结构对象，而不是vector
      HashTable<K,V> newHashTable;
      newHashTable.tables.resize(newCapacity);//不能使用reserve,因为reserve只更改了容量，没有改变size  vector插入的时候检查下标的合法性:i<_size ,会导致新位置不能插入
      for(int i = 0;i<tables.size();i++)
      {
        if(tables[i].status == EXIST)
          newHashTable.insert(tables[i]._kv);
      }
      //交换两个哈希表
      tables.swap(newHashTable.tables);
   }
   size_t start = kv.first % tables.size();//哈希地址
   int index = start;
   int i = 0;
   //找到状态为空或者状态为删除的位置进行插入
   while(tables[index].status == EXIST)
   {
    // 线性探测
    //  i++;
    //  index = (start + i) % tables.size();

     //二次探测
     i++;
     index = (start + i * i) % tables.size();
   }
   //当前位置状态为空,一定存在状态为空的位置，因为负载因子控制在0.7以下，也就是哈希表永远不会满载，
  tables[index]._kv = kv;
  tables[index].status =EXIST; //插入的时候记得修改状态！！！

  n++;
  return true;
  }
  Node* find(const K& key)
  {
    if(tables.size() == 0)
      return nullptr;
    size_t start = key % tables.size(); //哈希起始地址
    //从该位置开始线性探测/二次探测,如果提前遇到空位置还没有找到，说明哈希表没有该元素
    int index = start;
    int i = 0;
    while(tables[index].status != EMPTY)
    {
      if(tables[index]._kv.first == key && tables[index].status == EXIST)
          return &tables[index];
      //方法1:线性探测
      // i++;
      // //err写法:index = (index + i) % tables.size(); //线性探测,防止越界！
      // index = (start+i)%tables.size(); //不能是index+i,因为可能会跳跃式的到一个空位置，让一个存在的元素被判断为不存在
      //方法2:二次探测
      i++;
      index = (start + i*i ) %tables.size();
    }
    return nullptr;
  }
  bool erase(const K& key)
  {
    //删除一个元素：只需把该元素位置的状态设置为删除即可，这样在查找该元素的时候，因为该位置是删除的，所以是找不到的。
    //插入元素的时候，会找位置状态为空||删除的位置进行插入
    Node* ret = find(key);
    if(!ret)
      return false;
    n--;
    ret->status = DELETE;
    return true;
  }
  //for test
  //可以将哈希表的元素顺序打印出来观察是否正确
  void Print()
  {
    cout << "哈希表有效元素个数:" << n << endl;
    for(auto& node:tables)
      printf("[val_key:%d status:%d]\n",node._kv.first,node.status);
    cout << endl;
  } 
private:
  vector<Node> tables;
  size_t n = 0;//哈希表当中的有效元素个数
};
}
int main()
{
  vector<int> v{3,23,33,43,20,30}; 
  Mango::HashTable<int,int> ht;
  for(auto& n:v)
    ht.insert({n,n});
  ht.Print();
  ht.erase(3);
  ht.erase(23);
  ht.insert({53,53});
  cout << ht.find(3) << endl;
  cout << ht.find(23) << endl;
  ht.Print();
  return 0;
}
